\section{Resultados}
\label{sec::resultados}

Para las siguientes secciones, analizaremos la complejidad en peor caso
de cada m\'etodo, adem\'as de elegir los par\'ametros de la 
b\'squeda local y la metaheur\'istica.

Posteriormente comparar\'emos los distintos m\'etodos entre si con las
familias de grafos tomadas como peor caso para cada una.

Para medir la cantidad de  operaciones, tomamos el tiempo en ticks del 
reloj propio del sistema. Para ello utilizamos la funci\'on 
\texttt{clock} que es parte de la librer\'ia estandar de C++, que 
devuelve la cantidad de ticks de reloj que ha ejecutado el programa 
desde su inicio. Llamando a esta funci\'on al principio y al final de 
comenzar a resolver el grafo (desconsiderando el costo de leer el grafo 
y escribir la respuesta), tenemos una medida del tiempo insumido por el 
programa, en este caso en milisegundos puesto que un tick de reloj esta
definido como un mil\'esimo de segundo . Los resultados se tomaron sobre 
un promedio de 10 mediciones en todos los casos.

En todos los casos presentados la cantidad de aristas del grafo es 
$O(n)$ con $n$ la cantidad de v\'ertices y los mismos son conexos.

Esto se eligi\'o puesto que no nos result\'o posible encontrar ejemplos 
de grafos donde la cantidad de aristas  del grafo fuese cuadr\'atica 
en la cantidad de nodos y resultaran de inter\'es: A mayor n\'umero de 
aristas m\'as sencillo es para los m\'etodos presentados encontrar 
una soluci\'on \'optima r\'apida. Por ejemplo, si tomamos el caso de un
grafo completo $K_n$, el algoritmo exacto se llamar\'a recursivamente 
una vez al tomar cualquier nodo (puesto que esto constituye una 
soluci\'on) y encontrar\'a que esto es un conjunto dominante. Luego, al
mejorar la cota de cantidad de nodos del conjunto dominante a 1, se 
reduce muy dr\'asticamente (a $O(n)$ de hecho) la cantidad de llamadas
recursivas, puesto que ahora el algoritmo solo continuar\'a si la 
cantidad de elementos del conjunto dominante a examinar es 0 (
lo cual es imposible).

Por otro lado la raz\'on por la cual consideramos solamente grafos 
conexos es que un grafo conexo es siempre peor caso para nuestros
algoritmos. Esto se debe a que las cotas de complejidad obtenidas son
en todos los casos peores que lineal, con lo cual el costo de iterar 
sobre todas las componentes conexas (que es lineal por hacerse mediante 
un algoritmo Depth-First Search) es acotable por el costo mismo de 
resolver cada componetne conexa. Veremos esto m\'as formalmente en
el an\'alisis de cada caso. 

\subsection{Algoritmo exacto}

En primer lugar analizaremos experimentalmente la complejidad 
del algoritmo exacto para resolver el problema de m\'inimo 
conjunto dominante.

Primero observamos que el peor caso para el
algoritmo presentado consiste en un grafo conexo. Como vimos en la 
secci\'on~\ref{sec::exacto}, la complejidad del algoritmo para un grafo
conexo de $n$ v\'ertices y $m$ aristas es $O(m2^n)$. Supongamos que un
grafo tiene $c$ componentes conexas, con $n_1,n_2,\dots,n_c$ nodos y 
$m_1,m_2, \dots m_c$ aristas cada una. Tenemos que la complejidad de
resolver el problema con este m\'etodo es igual a la complejidad de 
obtener cada componente con DFS (lo cual es linear en la cantidad de 
nodos y aristas del gr\'afo) y luego resolver cada componente por 
separado. Adem\'as tenemos que

\[
\displaystyle \sum_{i = 1}^{c} m_i 2^n_i < \left (\sum_{i = 1}^{c} m_i \right )2^{\left ( \sum_{i = 1}^{c} 2^{n_i} \right )}
\]

Por lo tanto, como $O(n+m+m2^n) = O(m2^n)$, podemos considerar como 
peor caso el costo \'unicamente de aplicar m\'etodo explicado 
directamente sobre un grafo conexo de $n$ v\'ertices y $m$ aristas.

En base a este argumento elegimos como primer caso de estudio de peor
caso a la familia de grafos de camino: Un grafo de $n$ nodos y $m$ 
aristas es camino si cada nodo esta conectado con su anterior y 
siguiente en \'orden de ind\'ices (ver figura~\ref{fig::camino}).

\begin{figure}[H]
	\caption{Grafo camino de $n = 6$ nodos. Se utiliz\'o como ejemplo
	para mostrar el comportamiento exponencial del algoritmo exacto.}
	\label{fig::camino}
	\centering
	\includegraphics[width=0.2\textwidth]{img/camino.pdf}
\end{figure} 

Observemos que en este caso en particular, la cantidad de aristas del 
grafo es $O(n)$, al ser exactamente $n-1$. Por lo tanto, el an\'alisis
para este caso se puede hacer en funci\'on de $n$.

Para corroborar entonces nuestro an\'alisis te\'orico, corrimos el 
algoritmo sobre un conjunto de instancias de esta familia de grafos, 
$\forall n : n \geq 20 \wedge n \leq 36$.  
No fue posible en este caso realizar una cantidad de 
mediciones muy significativa, puesto que al ser la complejidad 
exponencial para $n \geq 36$ el algoritmo tardaba demasiado en terminar.
Al mismo tiempo, no se consideraron resultados con $n < 20$ puesto que 
el la cantidad de ciclos entre dos valores resulta insignificante 
frente a casos m\'as grandes.

El resultado puede verse en la Figura~\ref{fig::peorCasoExacto}. 
Incluimos tambi\'en una funci\'on de la familia $O(m2^n)$, para 
mostrar que efectivamente la cota te\'orica obtenida es v\'alida. 
Observese que no es asint\'oticamente \'optima, lo cual es consistente
con el an\'alisis realizado anteriormente (si consideramos que la 
cota tomada para la cantidad de llamadas recursivas al algoritmo de 
b\'usuqeda exhaustiva no es la mejor posible).

\begin{figure}[H]
	\caption{Cantidad de operaciones, medidas mediante variable 
	acumuladora, para el caso de un grafo camino de $n$ nodos y 
	$m = n-1$ aristas, en funci\'on de $n$. Se incluye una funci\'on
	de la familia $O(m2^n)$ para mostrar la validez de la cota en este caso.
	La escala del eje $y$ es logar\'itmica.}
	\label{fig::peorCasoExacto}
	\centering
	\includegraphics[width=\textwidth]{img/peorCasoExacto.pdf}
\end{figure} 

Para el caso del algoritmo exacto de resoluci\'on, no realizamos un 
estudio en profundida de la correctitud del mismo, puesto que la misma
es trivial por definici\'on: Siempre devuelve una soluci\'on correcta
pues explora todo el espacio de soluciones posibles y se queda con la
mejor.

Las corridas para los dem\'as grafos dieron resultados completamente 
an\'alogos al presentado aqu\'i y por brevedad no los incluimos.

\subsection{Algoritmo goloso}

El algoritmo goloso requiere de realizar dos an\'alisis emp\'iricos: 
La complejidad (experimental) del mismo, y la correctitud de las 
soluciones.

Para corroborar experimentalmente la complejidad en peor caso de este
m\'etodo tomamos la familia de grafos \textit{split graph} de $n$ nodos
independientes y $n$ nodos del completo. Un ejemplo de este tipo de 
grafo puede verse en la figura~\ref{fig::splitgraph}. Este grafo 
consiste de un grafo completo de $n$ nodos, y adem\'as cada uno de estos
$n$ nodos tiene un vecino del cual es el \'unico vecino.

\begin{figure}[H]
	\caption{Splitgraph de $n = 8$ nodos, $4$ en un conjunto 
	independiente y $4$ unidos en un clique.}
	\label{fig::splitgraph}
	\centering
	\includegraphics[width=0.4\textwidth]{img/splitgraph.pdf}
\end{figure} 


Nuevamente, consideramos esta familia de grafos conexos puesto que, al
ser la complejidad peor que lineal, tenemos que la misma empeora si
hay menos componentes conexas (de manera parecida a como mostramos que
ocurre para el algoritmo exacto).

Este caso es malo para el algoritmo puesto que el mismo debe iterar $n$
veces (porque debe ir agregando un nodo a la vez para dominar los nodos 
sueltos) y eso implica recorrer el grafo entero, que es casi un 
completo, cada vez que realiza esto.

Esta vez tomamos el grafo para $n,500 \leq n \leq 5000$, a 
intervalos de 200. Los resultados pueden verse en la 
figura~\ref{fig::peorCasoGoloso}, junto con un ajuste mediante una 
funci\'on de la familia $O(nm + n^2)$.

\begin{figure}[H]
	\caption{Cantidad de operaciones, medidas en ticks de reloj, para el 
	caso de un splitgraph de $n$ nodos, en funci\'on de 
	$n$. Se incluye una funci\'on de la familia $O(mn+n^2)$ para mostrar 
	la validez de la cota en este caso.}
	\label{fig::peorCasoGoloso}
	\centering
	\includegraphics[width=0.75\textwidth]{img/peorCasoGoloso.pdf}
\end{figure} 

Vemos entonces que para el caso considerado, el tiempo de ejecuci\'on
esta acotado por una funci\'on de la familia $O(mn+n^2)$ como predijimos
te\'oricamente.

Veamos ahora la calidad de la soluci\'on. Para ello, graficamos para 
el caso del contraejemplo presentado en la secci\'on~\ref{sec::greedy}
para la heur\'istica golosa constructiva, haciendo variar el $k$ de la
cantidad de nodos en el primer subnivel del \'arbol entre 500 y 2000,
a intervalos de 250.

Los resultados se presentan en la Figura~\ref{fig::calidadGoloso}. El 
tama\~no de la soluci\'on \'optima fue obtenido a mano (como ya 
describimos en la secci\'on~\ref{sec::greedy}). Como se puede ver, la 
soluci\'on devuelta por el algoritmo goloso no es correcta y se 
distancia en tama\~no de la soluci\'on correcta, pero no de manera 
acelerada sino al contrario. Esto concuerda con lo predicho 
te\'oricamente en la secci\'on~\ref{sec::greedy}.

\begin{figure}[H]
	\caption{Histograma del tama\~no de la soluci\'on devuelta por el
	algoritmo goloso constructivo, con respecto al tama\~no de la
	soluci\'on exacta, para instancias del grafo \'arbol 
	(ver Figura~\ref{fig::contragreedy}) con la cantidad de nodos 
	indicada.}
	\label{fig::calidadGoloso}
	\centering
	\includegraphics[width=0.75\textwidth]{img/calidadGoloso.pdf}
\end{figure} 

\subsection{Algoritmo de b\'usqueda local}

Para el caso de la b\'usqueda local, puesto que hemos dejado libre el 
par\'ametro de la cantidad de iteraciones m\'aximas sin mejorar de la 
misma, hemos de analizar el equilibrio entre el impacto de este valor
en la cantidad de iteraciones, y el impacto que esto tiene en la 
calidad de la soluci\'on.

Se intent\'o con varias familias de grafos, de las cuales encontramos
solo una donde los resultados de la b\'usqueda local y la soluci\'on
exacta no coincidieron, y donde m\'as a\'un la cantidad de iteraciones
de la b\'usqueda local tiene un fuerte impacto en la calidad de la 
soluci\'on.

La familia de grafos a considerar es la familia de grafos grilla 
cuadrados, como por ejemplo el grafo de la Figura~\ref{fig::grilla}
que corresponde al caso $n = 16$. Estos grafos tienen la particularidad
de que es muy dif\'icil conseguir el n\'umero exacto de dominancia. 
Para los casos con $n \leq 29$, pudimos consultar estos valores en la
tabla dada al final del paper~\cite{gridgraphs}.

\begin{figure}[H]
	\caption{Grafo grilla cuadriculado de $n = 16$ nodos.}
	\label{fig::grilla}
	\centering
	\includegraphics[width=0.4\textwidth]{img/grilla.pdf}
\end{figure} 

Empezaremos estudiando los valores obtenidos de la calidad de la 
soluc\'on de la b\'usqueda local en el caso del grafo grilla.

Presentamos, por su particularidad inter\'es, el gr\'afico de la calidad
de soluci\'on en funci\'on de la cantidad de iteraciones para el caso de
un grafo grilla de $12 \times 12$, junto con el valor exacto para esa 
grilla, obtenida del paper. 

\begin{figure}[H]
	\caption{Tama\~no del conjunto soluci\'on devuelto por la b\'usqueda
	local, en funci\'on de la cantidad de iteraciones, para el caso de
	un grafo grilla cuadrado de $12 \times 12$. Se incluye la 
	cardinalidad tambi\'en el m\'inimo conjunto dominante.}
	\label{fig::peorCasoCalidadLocal}
	\centering
	\includegraphics[width=0.8\textwidth]{img/peorCasoLocalCalidad.pdf}
\end{figure} 

Se cort\'o en esa cantidad de iteraciones puesto que para todas las
iteraciones posteriores no se percibi\'o diferencia en el tiempo de
ejecuci\'on del algoritmo ni en la calidad de la soluci\'on. Como 
podemos ver, la cantidad de iteraciones influye en la soluci\'on final y
de todos modos esta no alcanza a ser \'optima.

En el siguiente gr\'afico (Figura~\ref{fig::comparacionLocalGrilla}
incluimos tambi\'en, para grillas de distintos tama\~nos, cual fue la 
mejor soluci\'on obtenida (tomando como medida de esto el tama\~no de 
la soluci\'on alcanzada). En la Figura~\ref{fig::comparacionEntreLocalesGrilla}
ponemos una comparaci\'on de con cual cantidad de iteraciones se 
alcanz\'o la mejor soluci\'on observada. Estos gr\'aficos se realizaron
tomando como grafos de entrada los grafos grilla cuadrados de 
dimensiones entre 11 y 20 inclusive.

\begin{figure}[H]
	\caption{Comparaci\'on entre la mejor soluci\'on (es decir, con la 
	m\'axima cantidad de iteraciones intentada) mediante el m\'etodo de
	b\'usqueda local, frente al tama\~no de la soluci\'on exacta.}
	\label{fig::comparacionMejorLocalGrilla}
	\centering
	\includegraphics[width=0.8\textwidth]{img/comparacionEntreLocalesGrilla.pdf}
\end{figure}

\begin{figure}[H]
	\caption{Cantidad de iteraciones necesarias para que la b\'usqueda
	local obtuviera la mejor soluci\'on posible (es decir, que 
	incrementando la cantidad de iteraciones no se obtuviera una 
	soluci\'on mejor).}
	\label{fig::comparacionEntreLocalesGrilla}
	\centering
	\includegraphics[width=0.8\textwidth]{img/comparacionEntreLocalesGrilla.pdf}
\end{figure}

Como se puede observar, no hay a simple vista una correlaci\'on entre la 
cantidad de iteraciones necesarias y la cantidad de nodos del grafo grilla
cuadrado a resolver. Tampoco observamos que la soluci\'on obtenida por la 
b\'usqueda local empeore a medida que aumentan la cantidad de nodos del
grafo sobre el cual aplicamos la b\'usqueda local.

En base a esto, decidimos utilizar como criterio de parada de la 
b\'usqueda local, para an\'alisis futuros particularmente, la cantidad
de $\frac{n}{5}$. La elecci\'on de este valor es que es la fracci\'on
m\'as peque\~na de la cantidad de nodos de los grafo grilla vistos que
nos permite converger a la mejor soluci\'on (en especial considerando el
caso de un grafo grilla de $19 \times 19$).

Se intent\'o buscar otras familias de grafos donde se observara un 
comportamiento sub\'optimo para la b\'usqueda local, pero no se puedo
encontrar ninguna otra familia que exhibiera ese comportamiento, ya que
la cantidad de iteraciones de la b\'usqueda local necesarias result\'o 
muy reducida (incluso no necesit\'andose iterar, usando solamente 
remoci\'on de nodos del conjunto).

Habiendo entonces tomado esta decisi\'on en base al experimento 
realizado, procedemos entonces a corroborar la cota de complejidad 
presentada anteriormente.

Para ello usamos nuevamente como experimento el grafo grilla cuadrado.
Esta vez tomamos como dimensi\'on de la grilla valores entre 10 y 28 
inclusive.

El gr\'afico se incluye en la figura~\ref{fig::peorCasoLocalTiempos}.

\begin{figure}[H]
	\caption{Cantidad de ticks de reloj para la ejecuci\'on del 
	algoritmo de b\'usqueda local, con cantidad de iteraciones igual
	a un quinto de los nodos del grafo. Se incluye adem\'as un ajuste
	por funci\'on de la familia $O(n^4 + m n^3)$.}
	\label{fig::peorCasoLocalTiempos}
	\centering
	\includegraphics[width=0.8\textwidth]{img/peorCasoLocalTiempos.pdf}
\end{figure}

Se incluye adem\'as de las mediciones, una cota dentro de la familia
$O(n^4 + m n^3)$ para corroborar la validez de la cota presentada en 
las secciones anteriores.

\subsection{Algoritmo por metaheur\'istica GRASP}

Finalmente, examinaremos la implementaci\'on realizada de la 
metaheur\'istica GRASP. Para analizar la implementaci\'on y elegir los
par\'ametros utilizaremos nuevamente distintos grafos dentro de la 
familia de los grafos grilla, puesto que no nos fue posible encontrar 
una familia donde el algoritmo implementado tuviese errores (ya sea 
porque el algoritmo goloso encontraba una soluci\'on \'optima, o porque 
la b\'usqueda local pod\'ia mejorarla r\'apidamente).

Para la b\'usqueda local utilizamos el valor determinado anteriormente,
$\frac{n}{5}$ iteraciones.

Luego, para el an\'alisis decidimos utilizar una estrategia distinta a 
la realizada para la b\'usqueda local.

En este caso tomamos tres valores posibles del porcentaje: 10, 30 y 50,
y elegimos analizar tres valores posibles para la cantidad de 
iteraciones m\'aximas sin mejorar del GRASP: 
$\frac{n}{20}, \frac{n}{16}$ y $\frac{n}{4}$.

Los grafos grilla de $n^2$ nodos se consideraron con $n$ de dimensiones 
entre 5 y 20, para todos los valores intermedios entre ellos.

Para ninguno de los nueve casos se obtuvo una diferencia apreciable en
la calidad de sus soluciones, por lo tanto nos decidimos por un 
porcentaje de 30 sobre las soluciones, y una cantidad de iteraciones de
$\frac{n}{8}$ para la b\'usqueda local.

Un histograma con los resultados de la soluci\'on devuelta con respecto 
a la soluci\'on exacta por parte del m\'etodo GRASP puede verse 
en la Figura~\ref{fig::comparacionGrasp}. Al mismo tiempo, un gr\'afico
de la cantidad de ticks de reloj insumidos por el m\'etodo GRASP para
las instancias mencionadas anteriormente puede verse en la figura
~\ref{fig::tiempoGrasp}, junto con un ajuste de la familia dada por la
cota calculada anteriormente, y considerando los par\'ametros definidos
anteriormente.

Tambi\'en corrimos el m\'etodo GRASP sobre otras dos familias de grafos.
La primer familia fue la de los 

\subsection{Comparaci\'on entre los m\'etodos.}
